package algotithm.weekendrace.leetcode251.test4;

import java.util.*;

class Solution {
    public static void main(String[] args) {

    }

    Random random = new Random();
    Map<String, Long> map = new HashMap<>();
    Map<Long, Long> hash = new HashMap<>();
    Map<Long, Integer> occur = new HashMap<>();

    public long next() {
        return (long) Math.floor(random.nextDouble() * mod) % mod;
    }

    public long random(String s) {
        Long ans = map.get(s);
        if (ans == null) {
            ans = next();
            map.put(s, ans);
        }
        return ans;
    }

    public long hash(long v) {
        Long ans = hash.get(v);
        if (ans == null) {
            ans = next();
            hash.put(v, ans);
        }
        return ans;
    }

    long mod = 2305843009213693951L;

    public long sum(long a, long b) {
        long ans = a + b;
        if (ans >= mod) {
            ans -= mod;
        }
        return ans;
    }

    Node getNode(Node root, List<String> list, int i) {
        if (i == list.size()) {
            return root;
        }
        String name = list.get(i);
        Node next = root.adj.computeIfAbsent(name, Node::new);
        return getNode(next, list, i + 1);
    }

    long dfs(Node root) {
        long sum = 0;
        for (Node node : root.adj.values()) {
            sum = sum(sum, dfs(node));
        }
        root.childHash = hash(sum);
        root.hash = sum(random(root.name), hash(sum));
        occur.put(root.childHash, occur.getOrDefault(root.childHash, 0) + 1);
        return root.hash;
    }

    void tag(Node root, boolean delete) {
        if (root.adj.size() > 0 && occur.get(root.childHash) > 1) {
            delete = true;
        }
        root.deleted = delete;
        for (Node node : root.adj.values()) {
            tag(node, delete);
        }
    }

    void collect(Node root, List<String> path, List<List<String>> collector) {
        if (root.deleted) {
            return;
        }
        path.add(root.name);
        collector.add(new ArrayList<>(path.subList(1, path.size())));
        for (Node node : root.adj.values()) {
            collect(node, path, collector);
        }
        path.remove(path.size() - 1);
    }


    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
        Node root = new Node("");
        for (List<String> p : paths) {
            getNode(root, p, 0);
        }
        List<List<String>> res = new ArrayList<>();
        dfs(root);
        tag(root, false);
        collect(root, new ArrayList<>(), res);
        return res.subList(1, res.size());
    }
}


class Node {
    String name;

    public Node(String name) {
        this.name = name;
    }

    long hash;
    long childHash;
    boolean deleted;
    Map<String, Node> adj = new LinkedHashMap<>();
}